package leetcode.year2021.month12;

// 5. 最长回文子串
public class _03_3LongestPalindrome5 {
  /**
   * 思路： 逐个判断，从中往外延伸，求取最大值
   * @param s
   * @return
   */
  public String longestPalindrome1(String s) {
    int sn = s.length();
    char[] strs = s.toCharArray();
    int[] tempAnsInt = new int[]{0,0};
    int[] ansInt = tempAnsInt;
    int leftIndex;
    int rightIndex;
    for (int i = 0; i < sn; i++) {
      leftIndex = i;
      rightIndex = i;

      while (rightIndex < sn-1 && strs[i] == strs[rightIndex+1]){
        rightIndex++;
      }

      i = rightIndex;

      while (leftIndex > 0 && rightIndex < sn-1 && strs[leftIndex-1] == strs[rightIndex+1]){
        leftIndex--;
        rightIndex++;
      }

      tempAnsInt = new int[]{leftIndex,rightIndex};

      ansInt = tempAnsInt[1] - tempAnsInt[0] > ansInt[1] - ansInt[0] ? tempAnsInt : ansInt;
    }
    return s.substring(ansInt[0],ansInt[1]+1);
  }

  public String longestPalindrome(String s) {
    int sn = s.length();
    String ansPalindromeStr = "";
    String tempPalindromeStr;
    for (int i = 0; i < sn; i++) {
      tempPalindromeStr = getMaxLongestInCurrIndex(s,i);
      ansPalindromeStr = tempPalindromeStr.length() > ansPalindromeStr.length() ? tempPalindromeStr : ansPalindromeStr;
    }
    return ansPalindromeStr;
  }

  private String getMaxLongestInCurrIndex(String s, int i) {
    int sn = s.length();
    int leftIndex = i;
    int rightIndex = i;
    while (rightIndex < sn-1 && s.charAt(i) == s.charAt(rightIndex+1)){
      rightIndex++;
    }
    while (leftIndex > 0 && rightIndex < sn-1 && s.charAt(leftIndex-1) == s.charAt(rightIndex+1)){
      leftIndex--;
      rightIndex++;
    }
    return s.substring(leftIndex,rightIndex+1);
  }

  /**
   * 5. 最长回文子串
   * 给你一个字符串 s，找到 s 中最长的回文子串。
   *
   *
   *
   * 示例 1：
   *
   * 输入：s = "babad"
   * 输出："bab"
   * 解释："aba" 同样是符合题意的答案。
   * 示例 2：
   *
   * 输入：s = "cbbd"
   * 输出："bb"
   * 示例 3：
   *
   * 输入：s = "a"
   * 输出："a"
   * 示例 4：
   *
   * 输入：s = "ac"
   * 输出："a"
   *
   *
   * 提示：
   *
   * 1 <= s.length <= 1000
   * s 仅由数字和英文字母（大写和/或小写）组成
   */
}
